package com.zjsru.oneDay;

import java.util.*;

/**
 * 跳跃游戏 IV跳跃游戏 IV
 *  给你一个整数数组arr，你一开始在数组的第一个元素处（下标为 0）。
 *
 * 每一步，你可以从下标i跳到下标：
 *
 * i + 1满足：i + 1 < arr.length
 * i - 1满足：i - 1 >= 0
 * j满足：arr[i] == arr[j]且i != j
 * 请你返回到达数组最后一个元素的下标处所需的最少操作次数。
 *
 * 输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
 * 输出：3
 * 解释：那你需要跳跃 3 次，下标依次为 0 --> 4 --> 3 --> 9 。下标 9 为数组的最后一个元素的下标。
 *
 * 输入：arr = [7,6,9,6,9,6,9,7]
 * 输出：1
 * 解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。
 *
 * */
public class minJumps {
    public int minJumps(int[] arr) {
        Map<Integer, List<Integer>> idxSameValue = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < arr.length; i++) {
            idxSameValue.putIfAbsent(arr[i],new ArrayList<Integer>());
            idxSameValue.get(arr[i]).add(i);
        }
        Set<Integer> visitedIndex = new HashSet<Integer>();
        Queue<int[]> queue = new ArrayDeque<int[]>();
        queue.offer(new int[]{0,0});
        visitedIndex.add(0);
        while(!queue.isEmpty()){
            int[] idxSetp = queue.poll();
            int idx = idxSetp[0],step = idxSetp[1];
            if(idx == arr.length -1){
                return step;
            }
            int v = arr[idx];
            step++;
            if(idxSameValue.containsKey(v)){
                for (int i: idxSameValue.get(v)) {
                    if(visitedIndex.add(i)){
                        queue.offer(new int[]{i,step});
                    }
                }
               idxSameValue.remove(v);
            }
            if(idx + 1 < arr.length && visitedIndex.add(idx + 1)){
                queue.offer(new int[]{idx + 1, step});
            }
            if(idx - 1 >= 0 && visitedIndex.add(idx - 1)){
                queue.offer(new int[]{idx - 1,step});
            }
        }
            return -1;
    }
    public static void main(String[] args){
        minJumps minJumps = new minJumps();
        int[] arr = new int[]{100,-23,-23,404,100,23,23,23,3,404};
        System.out.println(minJumps.minJumps(arr));
    }
}
